package demo10;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

    //1.最长公共子序列(动态规划)
    public int longestCommonSubsequence(String text1, String text2) {
        //状态F(i, j) = 前i个t1的子串和前j个t2的子串的最长公共子序列长度
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }

    //2.剑指 Offer II 003. 前 n 个数字二进制中 1 的个数(动态规划)
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            if(i % 2 == 1) { //奇数
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = dp[i / 2];
            }
        }
        return dp;
    }

    //3.剑指 Offer II 088. 爬楼梯的最少成本(动态规划)
    public int minCostClimbingStairs(int[] cost) {
        //状态F(i):爬上低i层的最低花费
        //状态转移方程:F(i) = Math.min(F(i - 1), F(i - 2));
        int len = cost.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[len];
    }

    //4.剑指 Offer II 091. 粉刷房子(动态规划)
    public int minCost(int[][] costs) {
        int len = costs.length;
        for(int i = 1; i < len; i++) {
            costs[i][0] = Math.min(costs[i - 1][1], costs[i - 1][2]) + costs[i][0];
            costs[i][1] = Math.min(costs[i - 1][0], costs[i - 1][2]) + costs[i][1];
            costs[i][2] = Math.min(costs[i - 1][0], costs[i - 1][1]) + costs[i][2];
        }
        return Math.min(costs[len - 1][0], Math.min(costs[len - 1][1], costs[len - 1][2]));
    }
//
//    //5.剑指 Offer II 095. 最长公共子序列(dp)
//    public int longestCommonSubsequence(String text1, String text2) {
//        int len1 = text1.length();
//        int len2 = text2.length();
//        int[][] dp = new int[len1 + 1][len2 + 1];
//        for(int i = 1; i <= len1; i++) {
//            for(int j = 1; j <= len2; j++) {
//                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                } else {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
//                }
//            }
//        }
//        return dp[len1][len2];
//    }


    //6.将字符串翻转到单调递增(动态规划)
    public int minFlipsMonoIncr(String s) {
        int len = s.length();
        int[][] dp = new int[len][2];
        dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
        dp[0][1] = s.charAt(0) == '1' ? 0 : 1;
        for(int i = 1; i < len; i++) {
            if(s.charAt(i) == '0') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            } else {
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            }
        }
        return Math.min(dp[len - 1][0], dp[len - 1][1]);
    }

    //7.不同的二叉搜索树(动态规划)
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
//
//    //8.分割等和子集(动态规划)
//    public boolean canPartition(int[] nums) {
//        int sum = 0;
//        for(int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        if(sum % 2 != 0) {
//            return false;
//        }
//        int target = sum / 2;
//        int[][] dp = new int[nums.length][target + 1];
//        //初始化
//        for(int i = 0; i <= target; i++) {
//            if(nums[0] <= i) {
//                dp[0][i] = nums[0];
//            }
//        }
//
//        for(int i = 1; i < nums.length; i++) {
//            for(int j = 1; j <= target; j++) {
//                int no = dp[i - 1][j];//不选
//                int yes = 0;
//                if(j >= nums[i]) {//能放的下才选
//                    yes = dp[i - 1][j - nums[i]] + nums[i];
//                }
//                dp[i][j] = Math.max(no, yes);
//            }
//        }
//        if(dp[nums.length - 1][target] == target) {
//            return true;
//        }
//        return false;
//    }

    //8.分割等和子集(动态规划)
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target) {
            return true;
        }
        return false;
    }

    //9. 最后一块石头的重量(优先级队列)
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int len = stones.length;
        for(int i = 0; i < len; i++) {
            queue.add(stones[i]);
        }
        while(len > 1) {
            int a = queue.poll();
            int b = queue.poll();
            queue.add(a - b);
            len -= 1;
        }
        return queue.poll();
    }
//
//    //10.最后一块石头的重量 II(动态规划)
//    public int lastStoneWeightII(int[] stones) {
//        int sum = 0;
//        for(int num : stones) {
//            sum += num;
//        }
//        int target = sum / 2;
//        int len = stones.length;
//        int[][] dp = new int[len][target + 1];
//        for(int i = 0; i < len; i++) {
//            for(int j = 1; j <= target; j++) {
//                if(i == 0) { //初始化
//                    if(stones[0] <= j) {
//                        dp[i][j] = stones[0];
//                    }
//                } else { //递推
//                    int no = dp[i - 1][j];
//                    int yes = 0;
//                    if(stones[i] <= j) {
//                        yes = dp[i - 1][j - stones[i]] + stones[i];
//                    }
//                    dp[i][j] = Math.max(no, yes);
//                }
//            }
//        }
//        return sum - 2 * dp[stones.length - 1][target];
//    }

    //10.最后一块石头的重量 II(动态规划)
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int num : stones) {
            sum += num;
        }
        int target = sum / 2;
        int len = stones.length;
        int[] dp = new int[target + 1];
        for(int i = 0; i < len; i++) {
            for(int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
//
//    //目标和(0-1背包 - 2维)
//    public int findTargetSumWays(int[] nums, int target) {
//        int sum = 0;
//        for(int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        if((sum + target) % 2 != 0 || (Math.abs(target)>sum)) {
//            return 0;
//        }
//        int count = 0;
//        int ans = (sum + target) / 2;
//        int[][] dp = new int[nums.length][ans + 1];
//        //初始化
//        if(nums[0] == 0) {
//            dp[0][0] = 2;
//        } else {
//            dp[0][0] = 1;
//        }
//        for(int j = 1; j <= ans; j++) {
//            if(nums[0]==j) dp[0][j] = 1;
//        }
//        for(int i = 1; i < nums.length; i++) {
//            for(int j = 0; j <= ans; j++) {
//                int no = dp[i - 1][j];
//                int yes = 0;
//                if(nums[i] <= j) {
//                    yes = dp[i - 1][j - nums[i]];
//                }
//                dp[i][j] = no + yes;
//            }
//        }
//        return dp[nums.length - 1][ans];
//    }

    //目标和(0-1背包 - 1维)
    
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if((sum + target) % 2 == 1 || Math.abs(target) > sum) {
            return 0;
        }
        int ans = (sum + target) / 2;
        int[] dp = new int[ans + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++) {
            for(int j = ans; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[ans];
    }   
}

class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 1, 1, 1, 1};
        solution.findTargetSumWays(arr, 3);
    }
}